package grade;

import java.util.*;
import java.util.Map.Entry;
import java.util.ArrayList;
/**
 * Created by Alison on 2016/11/14.
 */
public class MostNum {
    /**
     * for debugging.
     */
    public static void main(String[] args) {
        int[] arr = {7, 3, 1, 4, 3, 6, 2, 8, 3, 2, 2, 2, 3, 4, 2};
        if (arr.length == 0) {
            System.out.println("等查找的数组为空.");
            return;
        }
        List<Integer> list  = new ArrayList<Integer>();
        for (int i = 0;i<10000000;i++){
            Random ran = new Random(1000);
            int num = ran.nextInt();
            list.add(num);
        }
        method3(list);
//        method2(arr);
    }

    //method 1
    public static void method1(int[] arr) {
        Arrays.sort(arr);   //升序

        //value,value_new值-1,为了使程序进入"不同元素值过渡"
        int count = 0, value = arr[0] - 1;            //保存最优元素信息
        int count_new = 0, value_new = arr[0] - 1;    //保存新搜寻元素信息
        for (int i = 0; i < arr.length; i++) {
            //连续相同的元素值
            if (arr[i] == value_new) {
                count_new++;
            }

            //不同元素值过渡或者扫描到数组末尾
            if (arr[i] != value_new || i == arr.length - 1) {
                //若新的元素值计数大于目前最优元素值计数时,更新
                if (count_new > count) {
                    count = count_new;
                    value = value_new;
                }

                //新的元素值
                value_new = arr[i];
                count_new = 1;
            }

        }
        display(value, count);
    }

    //method 2
    public static void method2(int[] arr) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        //遍历数组,记录相同数组值出现次数并存储在数据结构中
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i]))
                map.put(arr[i], map.get(arr[i]) + 1);
            else
                map.put(arr[i], 1);
        }

        //遍历数据结构,找出出现次数最多的元素.
        Set<Entry<Integer, Integer>> set = map.entrySet();
        Iterator<Entry<Integer, Integer>> it = set.iterator();
        boolean flag = true;    //判断是否第一次迭代
        int key = 0, value = 0;
        while (it.hasNext()) {
            Entry<Integer, Integer> e = it.next();

            //第一次遍历数据结构,先初始化key,value
            if (flag) {
                key = e.getKey();
                value = e.getValue();
                flag = false;
                continue;
            }

            //当前元素出现次数大于当前最优值的情况
            if (e.getValue() > value) {
                key = e.getKey();
                value = e.getValue();
            }
        }
        display(key, value);
    }
    //method 2
    public static int method3(List<Integer> arr) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        //遍历数组,记录相同数组值出现次数并存储在数据结构中
        for (int i = 0; i < arr.size(); i++) {
            if (map.containsKey(arr.get(i)))
                map.put(arr.get(i), map.get(arr.get(i)) + 1);
            else
                map.put(arr.get(i), 1);
        }

        //遍历数据结构,找出出现次数最多的元素.
        Set<Entry<Integer, Integer>> set = map.entrySet();
        Iterator<Entry<Integer, Integer>> it = set.iterator();
        boolean flag = true;    //判断是否第一次迭代
        int key = 0, value = 0;
        while (it.hasNext()) {
            Entry<Integer, Integer> e = it.next();

            //第一次遍历数据结构,先初始化key,value
            if (flag) {
                key = e.getKey();
                value = e.getValue();
                flag = false;
                continue;
            }

            //当前元素出现次数大于当前最优值的情况
            if (e.getValue() > value) {
                key = e.getKey();
                value = e.getValue();
            }
        }
//        display(key, value);
        return value;
    }

    //显示结果
    public static void display(int key, int value) {
        System.out.println("重复次数最多元素: " + key + "\t  重复次数:" + value);
    }
}